package org.example.SolutionNew005;

public class Backtrack005 {
    public static void main(String[] args) {
        Backtrack005 b = new Backtrack005();
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        System.out.println(b.exist(board,"DECCBF"));
    }

    boolean res;
    //board的灵活性可以使得该单词从任何地方发起攻击
    public boolean exist(char[][] board, String word) {
        res=false;
        boolean[][] visited = new boolean[board.length][board[0].length];
        char[] chars = word.toCharArray();
        for(int i = 0; i < board.length && !res; i++){
            for(int j = 0; j < board[0].length && !res; j++){
                searchTheNext(board,visited,i,j,chars,0);
            }
        }
        return res;
    }

    public void searchTheNext(char[][] board, boolean[][] visited, int x, int y, char[] chars,int index) {
        if(res) return;
        if(board[x][y]!=chars[index]) return;
        if(board[x][y]==chars[index]&&index==chars.length-1){
            res=true;
            return;
        }
        visited[x][y] = true;
        if(x>0&&!visited[x-1][y]){
            searchTheNext(board,visited,x-1,y,chars,index+1);
        }
        if(y>0&&!visited[x][y-1]){
            searchTheNext(board,visited,x,y-1,chars,index+1);
        }
        if(x<board.length-1&&!visited[x+1][y]){
            searchTheNext(board,visited,x+1,y,chars,index+1);
        }
        if(y<board[0].length-1&&!visited[x][y+1]){
            searchTheNext(board,visited,x,y+1,chars,index+1);
        }
        visited[x][y]=false;
    }


}
